#include <stdio.h>
#define LIST_MAX_SIZE 100
void move_of_list(int list[], int from_where, int num_elements)
{
    for (; from_where < num_elements; num_elements--)
    {
        list[num_elements] = list[num_elements - 1];
    }
}
int find_some_where(int list[], int find_this_num)
{
    int i = 0;
    while (1)
    {
        if (list[i] >= find_this_num)
        {
            return i;
        }
        i++;
    }
    return -1;
}
void insert_to_list(int list[], int from_where, int num_elements, int insert_this)
{
    move_of_list(list, from_where, num_elements);
    list[from_where] = insert_this;
}
void insertion_sort(int unsorted_array[], int num_elements)
{
    for (int i = 1; i < num_elements; i++)
    {
        if (unsorted_array[i] < unsorted_array[i - 1])
        {
            int place_to_insert = find_some_where(unsorted_array, unsorted_array[i]);
            insert_to_list(unsorted_array, place_to_insert, i, unsorted_array[i]);
        }
    }
}
void copy_to_list(int list_from[], int list_to[], int from_start, int to_start, int num_ele)
{
    for (int i = from_start, j = to_start, k = num_ele; k > 0; i++, j++, k--)
    {
        list_to[j] = list_from[i];
    }
}
void quick_sort(int unsorted_array[], int num_elements)
{
    int base_num = unsorted_array[0];
    if (num_elements > 1)
    {
        int small_num[LIST_MAX_SIZE], big_num[LIST_MAX_SIZE];
        int small_num_size = 0, big_num_size = 0;
        for (int i = 1; i < num_elements; i++)
        {
            if (base_num >= unsorted_array[i])
            {
                small_num[small_num_size] = unsorted_array[i];
                small_num_size++;
            }
            else
            {
                big_num[big_num_size] = unsorted_array[i];
                big_num_size++;
            }
        }
        unsorted_array[small_num_size] = base_num;
        quick_sort(small_num, small_num_size);
        quick_sort(big_num, big_num_size);
        copy_to_list(small_num, unsorted_array, 0, 0, small_num_size);
        copy_to_list(big_num, unsorted_array, 0, small_num_size + 1, big_num_size);
    }
}
void swap(int *a, int *b)

{
    int p;
    p = *a;
    *a = *b;
    *b = p;
}

void heap_builder(int arr[], int i, int len)
{
    int j = i * 2 + 1;
    while (j < len)
    {
        if (j + 1 < len && arr[j] < arr[j + 1])
        {
            j++;
        }
        if (arr[i] > arr[j])
        {
            break;
        }
        swap(&arr[i], &arr[j]);
        i = j;
        j = 2 * i + 1;
    }
}
void build_heap(int arr[], int n)
{
    int i;
    for (i = n / 2 - 1; i >= 0; i--)
    {
        heap_builder(arr, i, n);
    }
}
void heap_sort(int unsorted_array[], int num_elements)
{
    int i = 0;
    build_heap(unsorted_array, num_elements);
    for (i = num_elements - 1; i >= 0; i--)
    {
        swap(&unsorted_array[i], &unsorted_array[0]);
        heap_builder(unsorted_array, 0, i);
    }
}
int main()
{
    int a[] = {1, 9, 8, 7, 6, 5, 0, 2, 3, 4};
    for (int i = 0; i < 10; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
    heap_sort(a, 10);
    for (int i = 0; i < 10; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}